/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util.concurrent;

import java.io.Serializable;
import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

// BEGIN android-note
// removed link to collections framework docs
// END android-note

/**
 * A hash table supporting full concurrency of retrievals and
 * adjustable expected concurrency for updates. This class obeys the
 * same functional specification as {@link java.util.Hashtable}, and
 * includes versions of methods corresponding to each method of
 * <tt>Hashtable</tt>. However, even though all operations are
 * thread-safe, retrieval operations do <em>not</em> entail locking,
 * and there is <em>not</em> any support for locking the entire table
 * in a way that prevents all access.  This class is fully
 * interoperable with <tt>Hashtable</tt> in programs that rely on its
 * thread safety but not on its synchronization details.
 * <p>
 * <p> Retrieval operations (including <tt>get</tt>) generally do not
 * block, so may overlap with update operations (including
 * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
 * of the most recently <em>completed</em> update operations holding
 * upon their onset.  For aggregate operations such as <tt>putAll</tt>
 * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
 * removal of only some entries.  Similarly, Iterators and
 * Enumerations return elements reflecting the state of the hash table
 * at some point at or since the creation of the iterator/enumeration.
 * They do <em>not</em> throw {@link ConcurrentModificationException}.
 * However, iterators are designed to be used by only one thread at a time.
 * <p>
 * <p> The allowed concurrency among update operations is guided by
 * the optional <tt>concurrencyLevel</tt> constructor argument
 * (default <tt>16</tt>), which is used as a hint for internal sizing.  The
 * table is internally partitioned to try to permit the indicated
 * number of concurrent updates without contention. Because placement
 * in hash tables is essentially random, the actual concurrency will
 * vary.  Ideally, you should choose a value to accommodate as many
 * threads as will ever concurrently modify the table. Using a
 * significantly higher value than you need can waste space and time,
 * and a significantly lower value can lead to thread contention. But
 * overestimates and underestimates within an order of magnitude do
 * not usually have much noticeable impact. A value of one is
 * appropriate when it is known that only one thread will modify and
 * all others will only read. Also, resizing this or any other kind of
 * hash table is a relatively slow operation, so, when possible, it is
 * a good idea to provide estimates of expected table sizes in
 * constructors.
 * <p>
 * <p>This class and its views and iterators implement all of the
 * <em>optional</em> methods of the {@link Map} and {@link Iterator}
 * interfaces.
 * <p>
 * <p> Like {@link Hashtable} but unlike {@link HashMap}, this class
 * does <em>not</em> allow <tt>null</tt> to be used as a key or value.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 * @author Doug Lea
 * @since 1.5
 */
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {
	/*
	 * The basic strategy is to subdivide the table among Segments,
     * each of which itself is a concurrently readable hash table.  To
     * reduce footprint, all but one segments are constructed only
     * when first needed (see ensureSegment). To maintain visibility
     * in the presence of lazy construction, accesses to segments as
     * well as elements of segment's table must use volatile access,
     * which is done via Unsafe within methods segmentAt etc
     * below. These provide the functionality of AtomicReferenceArrays
     * but reduce the levels of indirection. Additionally,
     * volatile-writes of table elements and entry "next" fields
     * within locked operations use the cheaper "lazySet" forms of
     * writes (via putOrderedObject) because these writes are always
     * followed by lock releases that maintain sequential consistency
     * of table updates.
     *
     * Historical note: The previous version of this class relied
     * heavily on "final" fields, which avoided some volatile reads at
     * the expense of a large initial footprint.  Some remnants of
     * that design (including forced construction of segment 0) exist
     * to ensure serialization compatibility.
     */

    /* ---------------- Constants -------------- */

	/**
	 * The default initial capacity for this table,
	 * used when not otherwise specified in a constructor.
	 */
	static final int DEFAULT_INITIAL_CAPACITY = 16;

	/**
	 * The default load factor for this table, used when not
	 * otherwise specified in a constructor.
	 */
	static final float DEFAULT_LOAD_FACTOR = 0.75f;

	/**
	 * The default concurrency level for this table, used when not
	 * otherwise specified in a constructor.
	 */
	static final int DEFAULT_CONCURRENCY_LEVEL = 16;

	/**
	 * The maximum capacity, used if a higher value is implicitly
	 * specified by either of the constructors with arguments.  MUST
	 * be a power of two <= 1<<30 to ensure that entries are indexable
	 * using ints.
	 */
	static final int MAXIMUM_CAPACITY = 1 << 30;

	/**
	 * The minimum capacity for per-segment tables.  Must be a power
	 * of two, at least two to avoid immediate resizing on next use
	 * after lazy construction.
	 */
	static final int MIN_SEGMENT_TABLE_CAPACITY = 2;

	/**
	 * The maximum number of segments to allow; used to bound
	 * constructor arguments. Must be power of two less than 1 << 24.
	 */
	static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

	/**
	 * Number of unsynchronized retries in size and containsValue
	 * methods before resorting to locking. This is used to avoid
	 * unbounded retries if tables undergo continuous modification
	 * which would make it impossible to obtain an accurate result.
	 */
	static final int RETRIES_BEFORE_LOCK = 2;

    /* ---------------- Fields -------------- */

	/**
	 * Mask value for indexing into segments. The upper bits of a
	 * key's hash code are used to choose the segment.
	 */
	final int segmentMask;

	/**
	 * Shift value for indexing within segments.
	 */
	final int segmentShift;

	/**
	 * The segments, each of which is a specialized hash table.
	 */
	final Segment<K, V>[] segments;

	transient Set<K> keySet;
	transient Set<Entry<K, V>> entrySet;
	transient Collection<V> values;

	/**
	 * ConcurrentHashMap list entry. Note that this is never exported
	 * out as a user-visible Map.Entry.
	 */
	static final class HashEntry<K, V> {
		final int hash;
		final K key;
		volatile V value;
		volatile HashEntry<K, V> next;

		HashEntry(int hash, K key, V value, HashEntry<K, V> next) {
			this.hash = hash;
			this.key = key;
			this.value = value;
			this.next = next;
		}

		/**
		 * Sets next field with volatile write semantics.  (See above
		 * about use of putOrderedObject.)
		 */
		final void setNext(HashEntry<K, V> n) {
			this.next = n;
		}
	}

	/**
	 * Gets the ith element of given table (if nonnull) with volatile
	 * read semantics. Note: This is manually integrated into a few
	 * performance-sensitive methods to reduce call overhead.
	 */
	@SuppressWarnings("unchecked")
	static final <K, V> HashEntry<K, V> entryAt(HashEntry<K, V>[] tab, int i) {
		return tab != null ? tab[i] : null;
	}

	/**
	 * Sets the ith element of given table, with volatile write
	 * semantics. (See above about use of putOrderedObject.)
	 */
	static final <K, V> void setEntryAt(HashEntry<K, V>[] tab, int i,
										HashEntry<K, V> e) {
		tab[i] = e;
	}

	/**
	 * Applies a supplemental hash function to a given hashCode, which
	 * defends against poor quality hash functions.  This is critical
	 * because ConcurrentHashMap uses power-of-two length hash tables,
	 * that otherwise encounter collisions for hashCodes that do not
	 * differ in lower or upper bits.
	 */
	private static int hash(int h) {
		// Spread bits to regularize both segment and index locations,
		// using variant of single-word Wang/Jenkins hash.
		h += (h << 15) ^ 0xffffcd7d;
		h ^= (h >>> 10);
		h += (h << 3);
		h ^= (h >>> 6);
		h += (h << 2) + (h << 14);
		return h ^ (h >>> 16);
	}

	/**
	 * Segments are specialized versions of hash tables.  This
	 * subclasses from ReentrantLock opportunistically, just to
	 * simplify some locking and avoid separate construction.
	 */
	static final class Segment<K, V> extends ReentrantLock implements Serializable {
		/*
         * Segments maintain a table of entry lists that are always
         * kept in a consistent state, so can be read (via volatile
         * reads of segments and tables) without locking.  This
         * requires replicating nodes when necessary during table
         * resizing, so the old lists can be traversed by readers
         * still using old version of table.
         *
         * This class defines only mutative methods requiring locking.
         * Except as noted, the methods of this class perform the
         * per-segment versions of ConcurrentHashMap methods.  (Other
         * methods are integrated directly into ConcurrentHashMap
         * methods.) These mutative methods use a form of controlled
         * spinning on contention via methods scanAndLock and
         * scanAndLockForPut. These intersperse tryLocks with
         * traversals to locate nodes.  The main benefit is to absorb
         * cache misses (which are very common for hash tables) while
         * obtaining locks so that traversal is faster once
         * acquired. We do not actually use the found nodes since they
         * must be re-acquired under lock anyway to ensure sequential
         * consistency of updates (and in any case may be undetectably
         * stale), but they will normally be much faster to re-locate.
         * Also, scanAndLockForPut speculatively creates a fresh node
         * to use in put if no node is found.
         */

		/**
		 * The maximum number of times to tryLock in a prescan before
		 * possibly blocking on acquire in preparation for a locked
		 * segment operation. On multiprocessors, using a bounded
		 * number of retries maintains cache acquired while locating
		 * nodes.
		 */
		static final int MAX_SCAN_RETRIES =
			Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;

		/**
		 * The per-segment table. Elements are accessed via
		 * entryAt/setEntryAt providing volatile semantics.
		 */
		transient volatile HashEntry<K, V>[] table;

		/**
		 * The number of elements. Accessed only either within locks
		 * or among other volatile reads that maintain visibility.
		 */
		transient int count;

		/**
		 * The total number of mutative operations in this segment.
		 * Even though this may overflows 32 bits, it provides
		 * sufficient accuracy for stability checks in CHM isEmpty()
		 * and size() methods.  Accessed only either within locks or
		 * among other volatile reads that maintain visibility.
		 */
		transient int modCount;

		/**
		 * The table is rehashed when its size exceeds this threshold.
		 * (The value of this field is always <tt>(int)(capacity *
		 * loadFactor)</tt>.)
		 */
		transient int threshold;

		/**
		 * The load factor for the hash table.  Even though this value
		 * is same for all segments, it is replicated to avoid needing
		 * links to outer object.
		 *
		 * @serial
		 */
		final float loadFactor;

		Segment(float lf, int threshold, HashEntry<K, V>[] tab) {
			this.loadFactor = lf;
			this.threshold = threshold;
			this.table = tab;
		}

		final V put(K key, int hash, V value, boolean onlyIfAbsent) {
			HashEntry<K, V> node = tryLock() ? null :
				scanAndLockForPut(key, hash, value);
			V oldValue;
			try {
				HashEntry<K, V>[] tab = table;
				int index = (tab.length - 1) & hash;
				HashEntry<K, V> first = entryAt(tab, index);
				for (HashEntry<K, V> e = first; ; ) {
					if (e != null) {
						K k;
						if ((k = e.key) == key ||
							(e.hash == hash && key.equals(k))) {
							oldValue = e.value;
							if (!onlyIfAbsent) {
								e.value = value;
								++modCount;
							}
							break;
						}
						e = e.next;
					} else {
						if (node != null)
							node.setNext(first);
						else
							node = new HashEntry<K, V>(hash, key, value, first);
						int c = count + 1;
						if (c > threshold && tab.length < MAXIMUM_CAPACITY)
							rehash(node);
						else
							setEntryAt(tab, index, node);
						++modCount;
						count = c;
						oldValue = null;
						break;
					}
				}
			} finally {
				unlock();
			}
			return oldValue;
		}

		/**
		 * Doubles size of table and repacks entries, also adding the
		 * given node to new table
		 */
		@SuppressWarnings("unchecked")
		private void rehash(HashEntry<K, V> node) {
            /*
             * Reclassify nodes in each list to new table.  Because we
             * are using power-of-two expansion, the elements from
             * each bin must either stay at same index, or move with a
             * power of two offset. We eliminate unnecessary node
             * creation by catching cases where old nodes can be
             * reused because their next fields won't change.
             * Statistically, at the default threshold, only about
             * one-sixth of them need cloning when a table
             * doubles. The nodes they replace will be garbage
             * collectable as soon as they are no longer referenced by
             * any reader thread that may be in the midst of
             * concurrently traversing table. Entry accesses use plain
             * array indexing because they are followed by volatile
             * table write.
             */
			HashEntry<K, V>[] oldTable = table;
			int oldCapacity = oldTable.length;
			int newCapacity = oldCapacity << 1;
			threshold = (int) (newCapacity * loadFactor);
			HashEntry<K, V>[] newTable =
				(HashEntry<K, V>[]) new HashEntry<?, ?>[newCapacity];
			int sizeMask = newCapacity - 1;
			for (int i = 0; i < oldCapacity; i++) {
				HashEntry<K, V> e = oldTable[i];
				if (e != null) {
					HashEntry<K, V> next = e.next;
					int idx = e.hash & sizeMask;
					if (next == null)   //  Single node on list
						newTable[idx] = e;
					else { // Reuse consecutive sequence at same slot
						HashEntry<K, V> lastRun = e;
						int lastIdx = idx;
						for (HashEntry<K, V> last = next;
							 last != null;
							 last = last.next) {
							int k = last.hash & sizeMask;
							if (k != lastIdx) {
								lastIdx = k;
								lastRun = last;
							}
						}
						newTable[lastIdx] = lastRun;
						// Clone remaining nodes
						for (HashEntry<K, V> p = e; p != lastRun; p = p.next) {
							V v = p.value;
							int h = p.hash;
							int k = h & sizeMask;
							HashEntry<K, V> n = newTable[k];
							newTable[k] = new HashEntry<K, V>(h, p.key, v, n);
						}
					}
				}
			}
			int nodeIndex = node.hash & sizeMask; // add the new node
			node.setNext(newTable[nodeIndex]);
			newTable[nodeIndex] = node;
			table = newTable;
		}

		/**
		 * Scans for a node containing given key while trying to
		 * acquire lock, creating and returning one if not found. Upon
		 * return, guarantees that lock is held. Unlike in most
		 * methods, calls to method equals are not screened: Since
		 * traversal speed doesn't matter, we might as well help warm
		 * up the associated code and accesses as well.
		 *
		 * @return a new node if key not found, else null
		 */
		private HashEntry<K, V> scanAndLockForPut(K key, int hash, V value) {
			HashEntry<K, V> first = entryForHash(this, hash);
			HashEntry<K, V> e = first;
			HashEntry<K, V> node = null;
			int retries = -1; // negative while locating node
			while (!tryLock()) {
				HashEntry<K, V> f; // to recheck first below
				if (retries < 0) {
					if (e == null) {
						if (node == null) // speculatively create node
							node = new HashEntry<K, V>(hash, key, value, null);
						retries = 0;
					} else if (key.equals(e.key))
						retries = 0;
					else
						e = e.next;
				} else if (++retries > MAX_SCAN_RETRIES) {
					lock();
					break;
				} else if ((retries & 1) == 0 &&
					(f = entryForHash(this, hash)) != first) {
					e = first = f; // re-traverse if entry changed
					retries = -1;
				}
			}
			return node;
		}

		/**
		 * Scans for a node containing the given key while trying to
		 * acquire lock for a remove or replace operation. Upon
		 * return, guarantees that lock is held.  Note that we must
		 * lock even if the key is not found, to ensure sequential
		 * consistency of updates.
		 */
		private void scanAndLock(Object key, int hash) {
			// similar to but simpler than scanAndLockForPut
			HashEntry<K, V> first = entryForHash(this, hash);
			HashEntry<K, V> e = first;
			int retries = -1;
			while (!tryLock()) {
				HashEntry<K, V> f;
				if (retries < 0) {
					if (e == null || key.equals(e.key))
						retries = 0;
					else
						e = e.next;
				} else if (++retries > MAX_SCAN_RETRIES) {
					lock();
					break;
				} else if ((retries & 1) == 0 &&
					(f = entryForHash(this, hash)) != first) {
					e = first = f;
					retries = -1;
				}
			}
		}

		/**
		 * Remove; match on key only if value null, else match both.
		 */
		final V remove(Object key, int hash, Object value) {
			if (!tryLock())
				scanAndLock(key, hash);
			V oldValue = null;
			try {
				HashEntry<K, V>[] tab = table;
				int index = (tab.length - 1) & hash;
				HashEntry<K, V> e = entryAt(tab, index);
				HashEntry<K, V> pred = null;
				while (e != null) {
					K k;
					HashEntry<K, V> next = e.next;
					if ((k = e.key) == key ||
						(e.hash == hash && key.equals(k))) {
						V v = e.value;
						if (value == null || value == v || value.equals(v)) {
							if (pred == null)
								setEntryAt(tab, index, next);
							else
								pred.setNext(next);
							++modCount;
							--count;
							oldValue = v;
						}
						break;
					}
					pred = e;
					e = next;
				}
			} finally {
				unlock();
			}
			return oldValue;
		}

		final boolean replace(K key, int hash, V oldValue, V newValue) {
			if (!tryLock())
				scanAndLock(key, hash);
			boolean replaced = false;
			try {
				HashEntry<K, V> e;
				for (e = entryForHash(this, hash); e != null; e = e.next) {
					K k;
					if ((k = e.key) == key ||
						(e.hash == hash && key.equals(k))) {
						if (oldValue.equals(e.value)) {
							e.value = newValue;
							++modCount;
							replaced = true;
						}
						break;
					}
				}
			} finally {
				unlock();
			}
			return replaced;
		}

		final V replace(K key, int hash, V value) {
			if (!tryLock())
				scanAndLock(key, hash);
			V oldValue = null;
			try {
				HashEntry<K, V> e;
				for (e = entryForHash(this, hash); e != null; e = e.next) {
					K k;
					if ((k = e.key) == key ||
						(e.hash == hash && key.equals(k))) {
						oldValue = e.value;
						e.value = value;
						++modCount;
						break;
					}
				}
			} finally {
				unlock();
			}
			return oldValue;
		}

		final void clear() {
			lock();
			try {
				HashEntry<K, V>[] tab = table;
				for (int i = 0; i < tab.length; i++)
					setEntryAt(tab, i, null);
				++modCount;
				count = 0;
			} finally {
				unlock();
			}
		}
	}

	// Accessing segments

	@SuppressWarnings("unchecked")
	static final <K, V> Segment<K, V> segmentAt(Segment<K, V>[] ss, int j) {
		return ss == null ? null : ss[j];
	}

	/**
	 * Returns the segment for the given index, creating it and
	 * recording in segment table (via CAS) if not already present.
	 *
	 * @param k the index
	 * @return the segment
	 */
	@SuppressWarnings("unchecked")
	private Segment<K, V> ensureSegment(int k) {
		final Segment<K, V>[] ss = this.segments;
		int u = k; // raw offset
		Segment<K, V> seg;
		if ((seg = (Segment<K, V>) ss[u]) == null) {
			Segment<K, V> proto = ss[0]; // use segment 0 as prototype
			int cap = proto.table.length;
			float lf = proto.loadFactor;
			int threshold = (int) (cap * lf);
			HashEntry<K, V>[] tab = (HashEntry<K, V>[]) new HashEntry<?, ?>[cap];
			if ((seg = (Segment<K, V>) ss[u])
				== null) { // recheck
				Segment<K, V> s = new Segment<K, V>(lf, threshold, tab);
				while ((seg = (Segment<K, V>) ss[u])
					== null) {
					if (ss[u] == null) {
						ss[u] = seg = s;
						break;
					}
				}
			}
		}
		return seg;
	}

	// Hash-based segment and entry accesses

	/**
	 * Gets the segment for the given hash code.
	 */
	@SuppressWarnings("unchecked")
	private Segment<K, V> segmentForHash(int h) {
		int u = ((h >>> segmentShift) & segmentMask);
		return (Segment<K, V>) segments[u];
	}

	/**
	 * Gets the table entry for the given segment and hash code.
	 */
	@SuppressWarnings("unchecked")
	static final <K, V> HashEntry<K, V> entryForHash(Segment<K, V> seg, int h) {
		HashEntry<K, V>[] tab;
		return (seg == null || (tab = seg.table) == null) ? null : tab[tab.length - 1 & h];
	}

    /* ---------------- Public operations -------------- */

	/**
	 * Creates a new, empty map with the specified initial
	 * capacity, load factor and concurrency level.
	 *
	 * @param initialCapacity  the initial capacity. The implementation
	 *                         performs internal sizing to accommodate this many elements.
	 * @param loadFactor       the load factor threshold, used to control resizing.
	 *                         Resizing may be performed when the average number of elements per
	 *                         bin exceeds this threshold.
	 * @param concurrencyLevel the estimated number of concurrently
	 *                         updating threads. The implementation performs internal sizing
	 *                         to try to accommodate this many threads.
	 * @throws IllegalArgumentException if the initial capacity is
	 *                                  negative or the load factor or concurrencyLevel are
	 *                                  nonpositive.
	 */
	@SuppressWarnings("unchecked")
	public ConcurrentHashMap(int initialCapacity,
							 float loadFactor, int concurrencyLevel) {
		if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
			throw new IllegalArgumentException();
		if (concurrencyLevel > MAX_SEGMENTS)
			concurrencyLevel = MAX_SEGMENTS;
		// Find power-of-two sizes best matching arguments
		int sshift = 0;
		int ssize = 1;
		while (ssize < concurrencyLevel) {
			++sshift;
			ssize <<= 1;
		}
		this.segmentShift = 32 - sshift;
		this.segmentMask = ssize - 1;
		if (initialCapacity > MAXIMUM_CAPACITY)
			initialCapacity = MAXIMUM_CAPACITY;
		int c = initialCapacity / ssize;
		if (c * ssize < initialCapacity)
			++c;
		int cap = MIN_SEGMENT_TABLE_CAPACITY;
		while (cap < c)
			cap <<= 1;
		// create segments and segments[0]
		Segment<K, V> s0 =
			new Segment<K, V>(loadFactor, (int) (cap * loadFactor),
				(HashEntry<K, V>[]) new HashEntry<?, ?>[cap]);
		Segment<K, V>[] ss = (Segment<K, V>[]) new Segment<?, ?>[ssize];
		ss[0] = s0;
		this.segments = ss;
	}

	/**
	 * Creates a new, empty map with the specified initial capacity
	 * and load factor and with the default concurrencyLevel (16).
	 *
	 * @param initialCapacity The implementation performs internal
	 *                        sizing to accommodate this many elements.
	 * @param loadFactor      the load factor threshold, used to control resizing.
	 *                        Resizing may be performed when the average number of elements per
	 *                        bin exceeds this threshold.
	 * @throws IllegalArgumentException if the initial capacity of
	 *                                  elements is negative or the load factor is nonpositive
	 * @since 1.6
	 */
	public ConcurrentHashMap(int initialCapacity, float loadFactor) {
		this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
	}

	/**
	 * Creates a new, empty map with the specified initial capacity,
	 * and with default load factor (0.75) and concurrencyLevel (16).
	 *
	 * @param initialCapacity the initial capacity. The implementation
	 *                        performs internal sizing to accommodate this many elements.
	 * @throws IllegalArgumentException if the initial capacity of
	 *                                  elements is negative.
	 */
	public ConcurrentHashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
	}

	/**
	 * Creates a new, empty map with a default initial capacity (16),
	 * load factor (0.75) and concurrencyLevel (16).
	 */
	public ConcurrentHashMap() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
	}

	/**
	 * Creates a new map with the same mappings as the given map.
	 * The map is created with a capacity of 1.5 times the number
	 * of mappings in the given map or 16 (whichever is greater),
	 * and a default load factor (0.75) and concurrencyLevel (16).
	 *
	 * @param m the map
	 */
	public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
		this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
			DEFAULT_INITIAL_CAPACITY),
			DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
		putAll(m);
	}

	/**
	 * Returns <tt>true</tt> if this map contains no key-value mappings.
	 *
	 * @return <tt>true</tt> if this map contains no key-value mappings
	 */
	public boolean isEmpty() {
        /*
         * Sum per-segment modCounts to avoid mis-reporting when
         * elements are concurrently added and removed in one segment
         * while checking another, in which case the table was never
         * actually empty at any point. (The sum ensures accuracy up
         * through at least 1<<31 per-segment modifications before
         * recheck.)  Methods size() and containsValue() use similar
         * constructions for stability checks.
         */
		long sum = 0L;
		final Segment<K, V>[] segments = this.segments;
		for (int j = 0; j < segments.length; ++j) {
			Segment<K, V> seg = segmentAt(segments, j);
			if (seg != null) {
				if (seg.count != 0)
					return false;
				sum += seg.modCount;
			}
		}
		if (sum != 0L) { // recheck unless no modifications
			for (int j = 0; j < segments.length; ++j) {
				Segment<K, V> seg = segmentAt(segments, j);
				if (seg != null) {
					if (seg.count != 0)
						return false;
					sum -= seg.modCount;
				}
			}
			if (sum != 0L)
				return false;
		}
		return true;
	}

	/**
	 * Returns the number of key-value mappings in this map.  If the
	 * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
	 * <tt>Integer.MAX_VALUE</tt>.
	 *
	 * @return the number of key-value mappings in this map
	 */
	public int size() {
		// Try a few times to get accurate count. On failure due to
		// continuous async changes in table, resort to locking.
		final Segment<K, V>[] segments = this.segments;
		final int segmentCount = segments.length;

		long previousSum = 0L;
		for (int retries = -1; retries < RETRIES_BEFORE_LOCK; retries++) {
			long sum = 0L;    // sum of modCounts
			long size = 0L;
			for (int i = 0; i < segmentCount; i++) {
				Segment<K, V> segment = segmentAt(segments, i);
				if (segment != null) {
					sum += segment.modCount;
					size += segment.count;
				}
			}
			if (sum == previousSum)
				return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
			previousSum = sum;
		}

		long size = 0L;
		for (int i = 0; i < segmentCount; i++) {
			Segment<K, V> segment = ensureSegment(i);
			segment.lock();
			size += segment.count;
		}
		for (int i = 0; i < segmentCount; i++)
			segments[i].unlock();
		return ((size >>> 31) == 0) ? (int) size : Integer.MAX_VALUE;
	}

	/**
	 * Returns the value to which the specified key is mapped,
	 * or {@code null} if this map contains no mapping for the key.
	 * <p>
	 * <p>More formally, if this map contains a mapping from a key
	 * {@code k} to a value {@code v} such that {@code key.equals(k)},
	 * then this method returns {@code v}; otherwise it returns
	 * {@code null}.  (There can be at most one such mapping.)
	 *
	 * @throws NullPointerException if the specified key is null
	 */
	public V get(Object key) {
		Segment<K, V> s; // manually integrate access methods to reduce overhead
		HashEntry<K, V>[] tab;
		int h = hash(key.hashCode());
		int u = h >>> segmentShift & segmentMask;
		if ((s = segments[u]) != null &&
			(tab = s.table) != null) {
			for (HashEntry<K, V> e = tab[tab.length - 1 & h];
				 e != null; e = e.next) {
				K k;
				if ((k = e.key) == key || (e.hash == h && key.equals(k)))
					return e.value;
			}
		}
		return null;
	}

	/**
	 * Tests if the specified object is a key in this table.
	 *
	 * @param key possible key
	 * @return <tt>true</tt> if and only if the specified object
	 * is a key in this table, as determined by the
	 * <tt>equals</tt> method; <tt>false</tt> otherwise.
	 * @throws NullPointerException if the specified key is null
	 */
	@SuppressWarnings("unchecked")
	public boolean containsKey(Object key) {
		Segment<K, V> s; // same as get() except no need for volatile value read
		HashEntry<K, V>[] tab;
		int h = hash(key.hashCode());
		int u = ((h >>> segmentShift & segmentMask));
		if ((s = (Segment<K, V>) segments[u]) != null &&
			(tab = s.table) != null) {
			for (HashEntry<K, V> e = tab[(((tab.length - 1) & h))];
				 e != null; e = e.next) {
				K k;
				if ((k = e.key) == key || (e.hash == h && key.equals(k)))
					return true;
			}
		}
		return false;
	}

	/**
	 * Returns <tt>true</tt> if this map maps one or more keys to the
	 * specified value. Note: This method requires a full internal
	 * traversal of the hash table, and so is much slower than
	 * method <tt>containsKey</tt>.
	 *
	 * @param value value whose presence in this map is to be tested
	 * @return <tt>true</tt> if this map maps one or more keys to the
	 * specified value
	 * @throws NullPointerException if the specified value is null
	 */
	public boolean containsValue(Object value) {
		// Same idea as size()
		if (value == null)
			throw new NullPointerException();
		final Segment<K, V>[] segments = this.segments;
		long previousSum = 0L;
		int lockCount = 0;
		try {
			for (int retries = -1; ; retries++) {
				long sum = 0L;    // sum of modCounts
				for (int j = 0; j < segments.length; j++) {
					Segment<K, V> segment;
					if (retries == RETRIES_BEFORE_LOCK) {
						segment = ensureSegment(j);
						segment.lock();
						lockCount++;
					} else {
						segment = segmentAt(segments, j);
						if (segment == null)
							continue;
					}
					HashEntry<K, V>[] tab = segment.table;
					if (tab != null) {
						for (int i = 0; i < tab.length; i++) {
							HashEntry<K, V> e;
							for (e = entryAt(tab, i); e != null; e = e.next) {
								V v = e.value;
								if (v != null && value.equals(v))
									return true;
							}
						}
						sum += segment.modCount;
					}
				}
				if ((retries >= 0 && sum == previousSum) || lockCount > 0)
					return false;
				previousSum = sum;
			}
		} finally {
			for (int j = 0; j < lockCount; j++)
				segments[j].unlock();
		}
	}

	/**
	 * Legacy method testing if some key maps into the specified value
	 * in this table.  This method is identical in functionality to
	 * {@link #containsValue}, and exists solely to ensure
	 * full compatibility with class {@link java.util.Hashtable},
	 * which supported this method prior to introduction of the
	 * Java Collections framework.
	 *
	 * @param value a value to search for
	 * @return <tt>true</tt> if and only if some key maps to the
	 * <tt>value</tt> argument in this table as
	 * determined by the <tt>equals</tt> method;
	 * <tt>false</tt> otherwise
	 * @throws NullPointerException if the specified value is null
	 */
	public boolean contains(Object value) {
		return containsValue(value);
	}

	/**
	 * Maps the specified key to the specified value in this table.
	 * Neither the key nor the value can be null.
	 * <p>
	 * <p> The value can be retrieved by calling the <tt>get</tt> method
	 * with a key that is equal to the original key.
	 *
	 * @param key   key with which the specified value is to be associated
	 * @param value value to be associated with the specified key
	 * @return the previous value associated with <tt>key</tt>, or
	 * <tt>null</tt> if there was no mapping for <tt>key</tt>
	 * @throws NullPointerException if the specified key or value is null
	 */
	@SuppressWarnings("unchecked")
	public V put(K key, V value) {
		Segment<K, V> s;
		if (value == null)
			throw new NullPointerException();
		int hash = hash(key.hashCode());
		int j = (hash >>> segmentShift) & segmentMask;
		if ((s = segments[j]) == null) //  in ensureSegment
			s = ensureSegment(j);
		return s.put(key, hash, value, false);
	}

	/**
	 * {@inheritDoc}
	 *
	 * @return the previous value associated with the specified key,
	 * or <tt>null</tt> if there was no mapping for the key
	 * @throws NullPointerException if the specified key or value is null
	 */
	@SuppressWarnings("unchecked")
	public V putIfAbsent(K key, V value) {
		Segment<K, V> s;
		if (value == null)
			throw new NullPointerException();
		int hash = hash(key.hashCode());
		int j = (hash >>> segmentShift) & segmentMask;
		if ((s = segments[j]) == null)
			s = ensureSegment(j);
		return s.put(key, hash, value, true);
	}

	/**
	 * Copies all of the mappings from the specified map to this one.
	 * These mappings replace any mappings that this map had for any of the
	 * keys currently in the specified map.
	 *
	 * @param m mappings to be stored in this map
	 */
	public void putAll(Map<? extends K, ? extends V> m) {
		for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
			put(e.getKey(), e.getValue());
	}

	/**
	 * Removes the key (and its corresponding value) from this map.
	 * This method does nothing if the key is not in the map.
	 *
	 * @param key the key that needs to be removed
	 * @return the previous value associated with <tt>key</tt>, or
	 * <tt>null</tt> if there was no mapping for <tt>key</tt>
	 * @throws NullPointerException if the specified key is null
	 */
	public V remove(Object key) {
		int hash = hash(key.hashCode());
		Segment<K, V> s = segmentForHash(hash);
		return s == null ? null : s.remove(key, hash, null);
	}

	/**
	 * {@inheritDoc}
	 *
	 * @throws NullPointerException if the specified key is null
	 */
	public boolean remove(Object key, Object value) {
		int hash = hash(key.hashCode());
		Segment<K, V> s;
		return value != null && (s = segmentForHash(hash)) != null &&
			s.remove(key, hash, value) != null;
	}

	/**
	 * {@inheritDoc}
	 *
	 * @throws NullPointerException if any of the arguments are null
	 */
	public boolean replace(K key, V oldValue, V newValue) {
		int hash = hash(key.hashCode());
		if (oldValue == null || newValue == null)
			throw new NullPointerException();
		Segment<K, V> s = segmentForHash(hash);
		return s != null && s.replace(key, hash, oldValue, newValue);
	}

	/**
	 * {@inheritDoc}
	 *
	 * @return the previous value associated with the specified key,
	 * or <tt>null</tt> if there was no mapping for the key
	 * @throws NullPointerException if the specified key or value is null
	 */
	public V replace(K key, V value) {
		int hash = hash(key.hashCode());
		if (value == null)
			throw new NullPointerException();
		Segment<K, V> s = segmentForHash(hash);
		return s == null ? null : s.replace(key, hash, value);
	}

	/**
	 * Removes all of the mappings from this map.
	 */
	public void clear() {
		final Segment<K, V>[] segments = this.segments;
		for (int j = 0; j < segments.length; ++j) {
			Segment<K, V> s = segmentAt(segments, j);
			if (s != null)
				s.clear();
		}
	}

	/**
	 * Returns a {@link Set} view of the keys contained in this map.
	 * The set is backed by the map, so changes to the map are
	 * reflected in the set, and vice-versa.  The set supports element
	 * removal, which removes the corresponding mapping from this map,
	 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
	 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
	 * operations.  It does not support the <tt>add</tt> or
	 * <tt>addAll</tt> operations.
	 * <p>
	 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
	 * that will never throw {@link ConcurrentModificationException},
	 * and guarantees to traverse elements as they existed upon
	 * construction of the iterator, and may (but is not guaranteed to)
	 * reflect any modifications subsequent to construction.
	 */
	public Set<K> keySet() {
		Set<K> ks = keySet;
		return (ks != null) ? ks : (keySet = new KeySet());
	}

	/**
	 * Returns a {@link Collection} view of the values contained in this map.
	 * The collection is backed by the map, so changes to the map are
	 * reflected in the collection, and vice-versa.  The collection
	 * supports element removal, which removes the corresponding
	 * mapping from this map, via the <tt>Iterator.remove</tt>,
	 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
	 * <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not
	 * support the <tt>add</tt> or <tt>addAll</tt> operations.
	 * <p>
	 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
	 * that will never throw {@link ConcurrentModificationException},
	 * and guarantees to traverse elements as they existed upon
	 * construction of the iterator, and may (but is not guaranteed to)
	 * reflect any modifications subsequent to construction.
	 */
	public Collection<V> values() {
		Collection<V> vs = values;
		return (vs != null) ? vs : (values = new Values());
	}

	/**
	 * Returns a {@link Set} view of the mappings contained in this map.
	 * The set is backed by the map, so changes to the map are
	 * reflected in the set, and vice-versa.  The set supports element
	 * removal, which removes the corresponding mapping from the map,
	 * via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
	 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
	 * operations.  It does not support the <tt>add</tt> or
	 * <tt>addAll</tt> operations.
	 * <p>
	 * <p>The view's <tt>iterator</tt> is a "weakly consistent" iterator
	 * that will never throw {@link ConcurrentModificationException},
	 * and guarantees to traverse elements as they existed upon
	 * construction of the iterator, and may (but is not guaranteed to)
	 * reflect any modifications subsequent to construction.
	 */
	public Set<Entry<K, V>> entrySet() {
		Set<Entry<K, V>> es = entrySet;
		return (es != null) ? es : (entrySet = new EntrySet());
	}

	/**
	 * Returns an enumeration of the keys in this table.
	 *
	 * @return an enumeration of the keys in this table
	 * @see #keySet()
	 */
	public Enumeration<K> keys() {
		return new KeyIterator();
	}

	/**
	 * Returns an enumeration of the values in this table.
	 *
	 * @return an enumeration of the values in this table
	 * @see #values()
	 */
	public Enumeration<V> elements() {
		return new ValueIterator();
	}

    /* ---------------- Iterator Support -------------- */

	abstract class HashIterator {
		int nextSegmentIndex;
		int nextTableIndex;
		HashEntry<K, V>[] currentTable;
		HashEntry<K, V> nextEntry;
		HashEntry<K, V> lastReturned;

		HashIterator() {
			nextSegmentIndex = segments.length - 1;
			nextTableIndex = -1;
			advance();
		}

		/**
		 * Sets nextEntry to first node of next non-empty table
		 * (in backwards order, to simplify checks).
		 */
		final void advance() {
			for (; ; ) {
				if (nextTableIndex >= 0) {
					if ((nextEntry = entryAt(currentTable,
						nextTableIndex--)) != null)
						break;
				} else if (nextSegmentIndex >= 0) {
					Segment<K, V> seg = segmentAt(segments, nextSegmentIndex--);
					if (seg != null && (currentTable = seg.table) != null)
						nextTableIndex = currentTable.length - 1;
				} else
					break;
			}
		}

		final HashEntry<K, V> nextEntry() {
			HashEntry<K, V> e = nextEntry;
			if (e == null)
				throw new NoSuchElementException();
			lastReturned = e; // cannot assign until after null check
			if ((nextEntry = e.next) == null)
				advance();
			return e;
		}

		public final boolean hasNext() {
			return nextEntry != null;
		}

		public final boolean hasMoreElements() {
			return nextEntry != null;
		}

		public final void remove() {
			if (lastReturned == null)
				throw new IllegalStateException();
			ConcurrentHashMap.this.remove(lastReturned.key);
			lastReturned = null;
		}
	}

	final class KeyIterator
		extends HashIterator
		implements Iterator<K>, Enumeration<K> {
		public final K next() {
			return super.nextEntry().key;
		}

		public final K nextElement() {
			return super.nextEntry().key;
		}
	}

	final class ValueIterator
		extends HashIterator
		implements Iterator<V>, Enumeration<V> {
		public final V next() {
			return super.nextEntry().value;
		}

		public final V nextElement() {
			return super.nextEntry().value;
		}
	}

	/**
	 * Custom Entry class used by EntryIterator.next(), that relays
	 * setValue changes to the underlying map.
	 */
	final class WriteThroughEntry
		extends AbstractMap.SimpleEntry<K, V> {
		WriteThroughEntry(K k, V v) {
			super(k, v);
		}

		/**
		 * Sets our entry's value and writes through to the map. The
		 * value to return is somewhat arbitrary here. Since a
		 * WriteThroughEntry does not necessarily track asynchronous
		 * changes, the most recent "previous" value could be
		 * different from what we return (or could even have been
		 * removed in which case the put will re-establish). We do not
		 * and cannot guarantee more.
		 */
		public V setValue(V value) {
			if (value == null) throw new NullPointerException();
			V v = super.setValue(value);
			ConcurrentHashMap.this.put(getKey(), value);
			return v;
		}
	}

	final class EntryIterator
		extends HashIterator
		implements Iterator<Entry<K, V>> {
		public Map.Entry<K, V> next() {
			HashEntry<K, V> e = super.nextEntry();
			return new WriteThroughEntry(e.key, e.value);
		}
	}

	final class KeySet extends AbstractSet<K> {
		public Iterator<K> iterator() {
			return new KeyIterator();
		}

		public int size() {
			return ConcurrentHashMap.this.size();
		}

		public boolean isEmpty() {
			return ConcurrentHashMap.this.isEmpty();
		}

		public boolean contains(Object o) {
			return ConcurrentHashMap.this.containsKey(o);
		}

		public boolean remove(Object o) {
			return ConcurrentHashMap.this.remove(o) != null;
		}

		public void clear() {
			ConcurrentHashMap.this.clear();
		}
	}

	final class Values extends AbstractCollection<V> {
		public Iterator<V> iterator() {
			return new ValueIterator();
		}

		public int size() {
			return ConcurrentHashMap.this.size();
		}

		public boolean isEmpty() {
			return ConcurrentHashMap.this.isEmpty();
		}

		public boolean contains(Object o) {
			return ConcurrentHashMap.this.containsValue(o);
		}

		public void clear() {
			ConcurrentHashMap.this.clear();
		}
	}

	final class EntrySet extends AbstractSet<Entry<K, V>> {
		public Iterator<Entry<K, V>> iterator() {
			return new EntryIterator();
		}

		public boolean contains(Object o) {
			if (!(o instanceof Map.Entry))
				return false;
			Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
			V v = ConcurrentHashMap.this.get(e.getKey());
			return v != null && v.equals(e.getValue());
		}

		public boolean remove(Object o) {
			if (!(o instanceof Map.Entry))
				return false;
			Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
			return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
		}

		public int size() {
			return ConcurrentHashMap.this.size();
		}

		public boolean isEmpty() {
			return ConcurrentHashMap.this.isEmpty();
		}

		public void clear() {
			ConcurrentHashMap.this.clear();
		}
	}

    /* ---------------- Serialization Support -------------- */

	/**
	 * Saves the state of the <tt>ConcurrentHashMap</tt> instance to a
	 * stream (i.e., serializes it).
	 *
	 * @param s the stream
	 * @serialData the key (Object) and value (Object)
	 * for each key-value mapping, followed by a null pair.
	 * The key-value mappings are emitted in no particular order.
	 */
	private void writeObject(java.io.ObjectOutputStream s)
		throws java.io.IOException {
		// force all segments for serialization compatibility
		for (int k = 0; k < segments.length; ++k)
			ensureSegment(k);
		s.defaultWriteObject();

		final Segment<K, V>[] segments = this.segments;
		for (int k = 0; k < segments.length; ++k) {
			Segment<K, V> seg = segmentAt(segments, k);
			seg.lock();
			try {
				HashEntry<K, V>[] tab = seg.table;
				for (int i = 0; i < tab.length; ++i) {
					HashEntry<K, V> e;
					for (e = entryAt(tab, i); e != null; e = e.next) {
						s.writeObject(e.key);
						s.writeObject(e.value);
					}
				}
			} finally {
				seg.unlock();
			}
		}
		s.writeObject(null);
		s.writeObject(null);
	}

	/**
	 * Reconstitutes the <tt>ConcurrentHashMap</tt> instance from a
	 * stream (i.e., deserializes it).
	 *
	 * @param s the stream
	 */
	@SuppressWarnings("unchecked")
	private void readObject(java.io.ObjectInputStream s)
		throws java.io.IOException, ClassNotFoundException {
		s.defaultReadObject();

		// Re-initialize segments to be minimally sized, and let grow.
		int cap = MIN_SEGMENT_TABLE_CAPACITY;
		final Segment<K, V>[] segments = this.segments;
		for (int k = 0; k < segments.length; ++k) {
			Segment<K, V> seg = segments[k];
			if (seg != null) {
				seg.threshold = (int) (cap * seg.loadFactor);
				seg.table = (HashEntry<K, V>[]) new HashEntry<?, ?>[cap];
			}
		}

		// Read the keys and values, and put the mappings in the table
		for (; ; ) {
			K key = (K) s.readObject();
			V value = (V) s.readObject();
			if (key == null)
				break;
			put(key, value);
		}
	}
}
